import java.util.LinkedList;
import java.util.List;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/9
 * \* Time: 15:41
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 二叉树中和为某一值的路径 {
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;

          TreeNode() {
          }

          TreeNode(int val) {
              this.val = val;
          }

          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }
      LinkedList<List<Integer>> res=new LinkedList<>();
      LinkedList<Integer> path = new LinkedList<>();
      public List<List<Integer>> pathSum(TreeNode root, int target) {
          recur(root,target);
          return res;
      }
          void recur(TreeNode root, int tar) {
              if(root == null) {
                  return;
              }
              path.add(root.val);
              tar -= root.val;
              if(tar == 0 && root.left == null && root.right == null)
              {
                  res.add(new LinkedList(path));
              }
              recur(root.left, tar);
              recur(root.right, tar);
              path.removeLast();
          }

}